package Aleehot100;

import java.util.PriorityQueue;

/**
 * ClassName: c076
 * Package: Aleehot100
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/9/2 08:33
 * @Version 1.0
 * @Since 1.0
 */
public class C076 {
    public static void main(String[] args) {
        C076 c076 = new C076();
        c076.addNum(1);
        c076.addNum(2);
        c076.addNum(3);
        System.out.println(c076.findMedian());
    }

    public void c076() {
        minHeap.clear();
        maxHeap.clear();
    }

    static PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
    static PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    public void addNum(int num) {
        // 这个 <= 是很讲究的，请细研究
        if(maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }

        // 平衡堆
        if(Math.abs(maxHeap.size() - minHeap.size()) > 1) {
            if (maxHeap.size() > minHeap.size()) {
                minHeap.add(maxHeap.poll());
            } else {
                maxHeap.add(minHeap.poll());
            }
        }
    }

    // 找到中位数
    public double findMedian() {
        if (minHeap.size() == maxHeap.size()) {
            return (minHeap.peek() + maxHeap.peek()) / 2D;
        } else {
            return minHeap.size() > maxHeap.size() ? minHeap.peek() : maxHeap.peek();
        }
    }
}
